"""
Problem 14: https://projecteuler.net/problem=14

The following iterative sequence is defined for the set of positive integers:

    n → n/2 (n is even)
    n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

    13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains
10 terms. Although it has not been proved yet (Collatz Problem), it is thought
that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = Thonny Python3.8.3
@creat_time = 2022/5/7
'''


CHAINS = {1:1, 2:2, 4:3, 8:4}


# ****************************use recursion********************************
def chains(n: int) -> list:
    '''
    >>> chains(1)
    [1]
    >>> chains(2)
    [2, 1]
    >>> chains(16)
    [16, 8, 4, 2, 1]
    >>> chains(13)
    [13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
    >>> chains(2**8)
    [256, 128, 64, 32, 16, 8, 4, 2, 1]
    '''
    if n == 1:
        return [1]
    if n % 2 == 0:
        return [n] + chains(n >> 1)
    else:
        return [n] + chains(3*n + 1)
        
def chainsLen(n: int) -> int:
    '''
    chainsLen(n) = len(chains(n))
    
    >>> chainsLen(1)
    1
    >>> chainsLen(2)
    2
    >>> chainsLen(16)
    5
    >>> chainsLen(13)
    10
    >>> chainsLen(2**64)
    65
    >>> chainsLen(837799)
    525
    '''
    
    global CHAINS
   
    if n in CHAINS:
        return CHAINS[n]
    
    if n % 2 == 0:
        if n >> 1 in CHAINS:
            CHAINS[n] = 1 + CHAINS[n >> 1]
        else:
            CHAINS[n] = 1 + chainsLen(n >> 1)

    else:
        if 3*n+1 in CHAINS:
            CHAINS[n] = 1 + CHAINS[3*n+1]
        else:
            CHAINS[n] = 1 + chainsLen(3*n+1)
    
    return CHAINS[n]


def maxChain(n: int = 1000000) -> tuple:
    '''
    >>> maxChain(1)
    (1, 1)
    >>> maxChain(2)
    (2, 2)
    >>> maxChain(5)
    (3, 8)
    '''
    
    global CHAINS
    
    if n == 1:
        return (1,1)
    
    res = 2
    maxlen = 2
    for i in range(3, n+1):
        ci = chainsLen(i)
            
        if  ci > maxlen:
            maxlen = ci
            res = i
            
    return res,maxlen


# ****************************use backstepping********************************
def chainBackGenerator(depth: int = 32):
    '''
    According Collatz rule, repeatedly generate the pre-Number in chains.
    e.g. pre_N -> 10 -> 5 -> 16 ... -> 1, pre_N are 20,3
    
        depth      Collatz Numbers 
        ------------------------- 
        layer = 1, [1]
        layer = 2, [2]
        layer = 3, [4]
        layer = 4, [8]
        layer = 5, [16]
        layer = 6, [32,5]
        layer = 7, [64,10]
        layer = 8, [128,21,20,3]
        layer = 32, [2147483648,...], generate 6258 Collatz Numbers.
        
    Notice:
        1. For every layer, the max(also first) number is 2^(layer-1). 
           !!! Risk of data overflow
           
        2. According maxChain(1000000), the longest chain is (837799, 525). 
           In this function, that means computing chainBackGenerator(525). 
           !!! It is impossbile. 
    '''
    
    global CHAINS
    
    genNew = lambda n: (2*n, ) if (n-1) % 3 != 0 else (2*n, (n-1) // 3)
    
    layer = 4
    list_layer = [8]  # jump the case : 1 --> 4 --> 1
    
    while layer < depth:
        list_layer = [n for item in map(genNew, list_layer) for n in item if n != 4]  # exclude the case : 1 --> 4 --> 1
        # print(f'layer = {layer+1}, [{list_layer[0]},...], generate {len(CHAINS)} Collatz Numbers.')
        
        for n in list_layer:
            CHAINS[n] = layer + 1  # update CHAINS
                  
        layer += 1
# ****************************use backstepping********************************            




if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose = False)
    
    chainBackGenerator()
    
    print(f'Under one million, produces the longest chain, {maxChain()}')
    # (837799, 525)
    print(f'So far, we get the max Collatz Numbers is {max(CHAINS.keys())}.')
    # 18446744073709551616
    print(f'But the dict CHAINS just has {len(CHAINS)} numbers. ')  # 2169615
    print('For n = 1000000, it is enough, but is too small campared with the max number.')
    
    '''
    Under one million, produces the longest chain, (837799, 525)
    So far, we get the max Collatz Numbers is 18446744073709551616.
    But the dict CHAINS just has 2169615 numbers. 
    For n = 1000000, it is enough, but is too small campared with the max number.
    '''
    
    


    


